In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.

In this paper, we study the knowledge tightness of zero-knowledge proofs. To this end, we present a new measure for the knowledge tightness of zero-knowledge proofs and show that if a language L has a bounded round zero-knowledge proof with knowledge tightness t(|x|) 2 - |x|-c for some c 0, then L BPP and that any language L AM has a bounded round zero-knowledge proof with knowledge tightness t(|x|) 2-2-O(|x|) under the assumption that collision intractable hash functions exist. This implies that in the case of a bounded round zero-knowledge proof for a language L BPP, the optimal knowledge tightness is "2" unless AM = BPP. In addition, we show that any language L IP has an unbounded round zero-knowledge proof with knowledge tightness t(|x|) 1.5 under the assumption that nonuniformly secure probabilistic encryptions exist.

In this paper we investigate the AM languages that seem to be located outside NP co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in ΔP2 AM co-AM but is unlikely to be in NP co-NP, and that GH is in ΔP2 AM but is unlikely to be in NP co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those languages: Any language that is polynomial time truth-table reducible to GIP is in AM co-AM; GIP is in co-SZK if SZK co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in DP. Here DP is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.

Private information retrieval for k 1 databases (denoted by (k,l)-PIR for short) is a protocol that (1) a user sends an l tuple query to each of k noncommunicating replicated databases; (2) each database responds the user with an answer corresponding to the l tuple query; (3) the user privately retrieve any single bit out of the n bits of data stored in k databases. In this model, "privacy" implies that the user retrieves the bit he is interested in but releases to each database nothing about which bit he wishes to get. In general, the efficiency of (k,l)-PIR is measured by the total amount of bits exchanged between the user and the k databases, but few about its lower bounds are known except for restricted cases. In this paper, we classify (k,l)-PIR into a linear type, a multilinear type, and an affine type with respect to the relationship between queries to each database (made by the user) and answers to the user (made by each database), and show that (1) the lower bound for the communication complexity of any multilinear type (k,l)-PIR is Ω(n1/(l+1)) (Theorem 3.1); (2) the lower bound for the communication complexity of any linear type (k,l)-PIR is Ω(n) (Corollary 3.2); (3) the lower bound for the communication complexity of any affine type (k,l)-PIR is Ω(n1/(l+1)) (Theorem 4.2).

In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect ot oracle entropy and average case oracle measures. As main results. we show the following: (1) for any k(n) 1/poly (n), if a language L has perfect KC k(n) + n-ω(1) with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) 1/poly(n), if a language L has perfect KC k(n) + n-ω(1) with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has statistical KC k(n) + 1 + ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ο(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).

It was proven by Tompa and Woll that some specific random self-reducible problems have perfect zero-knowledge interactive proofs. In this paper, in order to determine a concrete set of random self-reducible problems, we consider a general problem of inverting a surjection from a finite group onto a finite set, and explore its random self-reducibility. The main result shows that there exist group-theoretic conditions for the random self-reducibility, and that any such random self-reducible problem has a perfect zero-knowledge interactive proof. By this result, some classes of random self-reducible problems are defined, and the inclusion relations among them are consequently clarified.

Checkers, self-testers, and self-correctors for a function f are powerful tools in designing programs that compute f. However, the relationships among them have not been known well. In this paper, we first show that (1) if oneway permutations exist, then there exists a language L that has a checker but does not have a self-corrector. We then introduce a novel notion of "self-improvers" that trans form a faulty program into a less faulty program, and show that (2) if a function f has a self-tester/corrector pair, then f has a self-improver. As the applications of self-improvers, we finally show that (3) if a function f has a self-tester/corrector pair, then f has a flexible self-tester and (4) if a function f has a self-tester/corrector pair, then f has self-improver that transforms a faulty program into an alomost correct program.

The recent burst growth of the Internet use overloads networking systems and degrades the quality of communications, e.g., bandwidth loss, packet drops, delay of responses, etc. To overcome such degradation of communication quality, the notion of Quality of Service (QoS) has received attention in practice. In general, QoS switches have several queues and each queue has several slots to store arriving packets. Since network traffic changes frequently, QoS switches need to control arriving packets to maximize the total priorities of transmitted packets, where the priorities are given by nonnegative values and correspond to the quality of service required to each packet. In this paper, we first derive the upper bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 1/α and 1, i.e., for any α ≥ 1, the algorithm TLH is (3-1/α)-competitive. This is a generalization of known results--for the case that packets have only priority 1 (α =1), the algorithm GREEDY (or TLH) is 2-competitive; for the case that packets have priorities between 0 and 1 (α = ∞), the algorithm TLH is 3-competitive. Then we consider the lower bounds for the competitive ratio of multi-queue preemptive QoS problem with priority between 0 and 1, and show that the competitive ratio of any multi-queue preemptive QoS algorithm is at least 1.514.

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set ej ⊆ V of items and assigns valuation w(ej) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.

Damgrd defined the notion of a collision intractable hash functions and showed that there exists a collection of collision intractable hash functions if there exists a collection of claw-free permutation pairs. For a long time, the necessary and sufficient condition for the existence of a collection of collision intractable hash functions has not been known, however, very recently Russell finally showed that there exists a collection of collision intractable hash functions iff there exists a collection of claw-free pseudo-permutation pairs. In this paper, we show an alternative necessary and sufficient condition for the existence of a collection of collision intractable hash functions, i.e., there exists a collection of collision intractable hash functions iff there exists a collection of distinction intractable pseudo-permutations.

A family C of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, a family C of permutations on [n]={1,2,. . . ,n} is said to be min-wise independent if for any (nonempty) X [n] and any x X, Pr ( min {π(X)} = π(x))= ||X||-1 when π is chosen uniformly at random from C, where ||A|| is the cardinality of a finite set A. For any integer n>0, it has been known that (1) ||C|| lcm(n,n-1,. . . ,2,1) = en-o(n) for any family C of min-wise independent permutations on [n]; (2) there exists a polynomial time samplable C family of min-wise independent permutations on [n] such that ||C|| 4n. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(n,n-1,. . . ,2,1) for each integer n>0 and how to construct such a family C of min-wise independent permutations for each integer n>0 if it exists. In this paper, we shall construct a family Fn of permutations for each integer n>0 and show that Fn is min-wise independent and ||Fn|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family Fn of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.

Let L{0,1}* be a language and let λL : {0,1}*{0,1} be the characteristic function of the language L, i.e., if x ∈ L, λL (x) = 1; otherwise,λL (x) = 0. In this paper, we consider an adaptive checker with a single program F (resp. noncommunicating multiple programs F1, F2,...) for λL that works even when an incorrect program F* (resp. incorrect noncommunicating multiple programs F*1,F*2,...) for λL adaptively behaves according to inputs previously provided to the program F* (resp. the programs F*1,F*2,...). We show that (1) for any language L, there exists an adaptive checker with a single program for λL iff L and respectively have competitive interactive proof systems; and (2) that for any language L, there exists an adaptive checker with noncommunicating multiple programs for λL iff L and respectively have function-restricted interactive proof systems. This implies that for any language L, adaptive chekers with noncommunicating multiple programs for λL are as powerful as static ones with a single program for λL.

We give a characterization for the intractability of hyperelliptic discrete logarithm problem from a viewpoint of computational complexity theory. It is shown that the language of which complexity is equivalent to that of the hyperelliptic discrete logarithm problem is in NP co-AM, and that especially for elliptic curves, the corresponding language is in NP co-NP. It should be noted here that the language of which complexity is equivalent to that of the discrete logarithm problem defined over the multiplicative group of a finite field is also characterized as in NP co-NP.